package Data_Structure.Stack;

import java.util.Stack;


/**
 * @className: Test2
 * @author: 芃
 * @description: 栈相关OJ习题
 * @date: 2023/8/21 16:27
 */
//4、实现一个最小栈
class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;
    public MinStack() {
        this.stack = new Stack<>();
        this.minStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty()){
            minStack.push(val);
        }else {
            int minTop = minStack.peek();
            if (val <= minTop){
                minStack.push(val);
            }
        }
    }

    public void pop() {
        int val = stack.pop();
        if (val == minStack.peek()){
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}
public class Test2 {
    public static void main(String[] args) {
        System.out.println("hello");
    }
    //6、用栈实现队列

    //5、用队列实现栈

    //3、括号匹配问题
    //①、左括号多
    //②、右括号多
    //③、左右括号不匹配
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        char[] chars = s.toCharArray();
        for (char c: chars) {
            if (c == '(' || c == '[' || c == '{'){
                stack.push(c);
            }else {
                if (stack.isEmpty()){
                    //右括号多了
                    return false;
                }else {
                    char top = stack.peek();
                    //匹配就弹出栈顶元素，不匹配就直接false
                    if (c == ')' && top == '('){
                        stack.pop();
                    }else if (c == ']' && top == '['){
                        stack.pop();
                    }else if (c == '}' && top == '{'){
                        stack.pop();
                    }else {
                        return false;
                    }
                }
            }
        }
        //左括号多了
        return stack.isEmpty();
    }
    //2、栈的压入弹出序列
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int k : pushed) {
            stack.push(k);
            while (j < popped.length && !stack.isEmpty() && stack.peek() == popped[j]) {
                stack.pop();
                j++;
            }
        }
        return j == popped.length && stack.isEmpty();
    }
    //1、逆波兰表达式求值
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String token : tokens) {
            if (token.equals("+") ||
                    token.equals("-") ||
                    token.equals("*") ||
                    token.equals("/")) {
                //如果是运算符，就弹出栈顶的两个元素进行计算
                int val1 = stack.pop();
                int val2 = stack.pop();
                int ret = 0;
                if (token.equals("+")){
                    ret = val2 + val1;
                }else if (token.equals("-")){
                    ret = val2 - val1;
                }else if (token.equals("*")){
                    ret = val2 * val1;
                }else {
                    ret = val2 / val1;
                }
                stack.push(ret);
            }else {
                //如果不是运算符，就压栈
                int val = Integer.parseInt(token);
                stack.push(val);
            }
        }
        //栈里面仅剩的元素就是计算结果
        return stack.pop();
    }
}
